//package test;
//
//public class AVLTree {
//    static class TreeNode {
//        public int val;
//        public int bf;
//        public TreeNode left;
//        public TreeNode right;
//        public TreeNode parent;
//
//        public TreeNode(int val) {
//            this.val = val;
//        }
//    }
//
//    public TreeNode root;
//
//    public boolean insert(int val) {
//        TreeNode node = new TreeNode(val);
//        if (root == null) {
//            root = node;
//            return true;
//        }
//
//        TreeNode parent = null;
//        TreeNode cur = root;
//        while (cur != null) {
//            if (cur.val < val) {
//                parent = cur;
//                cur = cur.right;
//            } else if (cur.val == val) {
//                return false;
//            } else {
//                parent = cur;
//                cur = cur.left;
//            }
//        }
//
//        if (parent.val < val) {
//            parent.right = node;
//        } else {
//            parent.left = node;
//        }
//
//        node.parent = parent;
//        cur = node;
//
//        while () {
//            if (cur == parent.right) {
//                parent.bf++;
//            } else {
//                parent.bf--;
//            }
//
//            if (parent.bf == 0) {
//                break;
//            } else if (parent.bf == 1 || parent.bf == -1) {
//                cur = parent;
//                parent = cur.parent;
//            } else {
//                if (parent.bf == 2) {
//                    if (cur.bf == 1) {
//
//                    } else {
//
//                    }
//                } else {
//                    if (cur.bf == -1) {
//                        rotateRight(parent);
//                    } else {
//
//                    }
//                }
//            }
//        }
//
//    }
//
//    public void rotateRight(TreeNode parent) {
//        TreeNode subL = parent.left;
//        TreeNode subLR = subL.right;
//
//        parent.left = subLR;
//        subL.right = parent;
//        if(subLR != null){
//            subLR.parent = parent;
//        }
//        subLR.parent = parent;
//        TreeNode pParent = parent.parent;
//        parent.parent = subL;
//
//        if(parent == root){
//            root = subL;
//            root.parent = null;
//        }else {
//            if(pParent.left == parent){
//                pParent.left = subL;
//            }else {
//                pParent.right = subL;
//            }
//
//            subL.parent = pParent;
//        }
//        subL.bf = 0;
//        parent.bf = 0;
//    }
//}
